package GreedyAlgorithmPackage;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author Lzm
 * @version 1.0
 */
public class partitionLabels_ {
  @Test
  public void partitionLabelsTest(){
    String s = "ababcbacadefegdehijhklij";
    System.out.println(partitionLabels(s));
  }

  public List<Integer> partitionLabels(String s) {
    List<Integer> result = new ArrayList<>();
    int[] hash = new int[26];
    //统计字符串s中每个字符的最后出现的位置如 abacbda中 字符a最后出现的位置是6
    for (int i = 0 ; i < s.length() ; i++){
      hash[s.charAt(i) - 'a'] = i;
    }

    //用right和left得出区间长度
    int left = 0 ;
    int right = 0;
    for (int i = 0 ; i < s.length() ; i++){
      right = Math.max(right,hash[s.charAt(i) - 'a']);
      if (i == right){
        result.add(right - left + 1);
        left = right + 1;
      }
    }
    return result;
  }
}
